package forth

/*
	输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

	参考以下这颗二叉搜索树：

		 5
		/ \
	   2   6
	  / \
	 1   3
	示例 1：

	输入: [1,6,3,2,5]
	输出: false
	示例 2：

	输入: [1,3,2,6,5]
	输出: true

	提示：

	数组长度 <= 1000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
// 递归、后序遍历、数组最后一个元素是根节点、倒序遍历数组、找到第一个比根节点小的数、以此为界进行递归
func VerifyPostorder(postorder []int) bool {
	return verifyPostorder(postorder)
}

// 1. 后序遍历数组、其最后一个元素一定是一棵树的根节点
func verifyPostorder(postorder []int) bool {
	if len(postorder) == 0 {
		return true
	}
	rootValue := postorder[len(postorder)-1]
	i := 0
	for ; i < len(postorder)-1; i++ {
		if rootValue < postorder[i] {
			break
		}
	}
	for j := i; j < len(postorder)-1; j++ {
		if postorder[j] < rootValue {
			return false
		}
	}
	return verifyPostorder(postorder[:i]) && verifyPostorder(postorder[i:len(postorder)-1])
}
